Problem

Time limit : 3sec / Memory limit : 256MB

题意：

有$m$个点围成一个圈，按顺时针编号为$1$到$m$，一开始可以固定一个位置$x$，每次操作可以往顺时针方向走一步或直接走到$x$。现在给出$n$个位置$a_{1…n}$，初始时在$a_1$，第$i$次要从$a_i$走到$a_{i+1}$，在$x$可以任意选择的情况下使总步数最小

door♂

Solution

对于从$a$走到$b$来说

若选择的$x=a $或$ a+1$，那么不会使步数减少
若选择的$x=a+2$，会使步数减少$1$
若选择的$x=a+3$，会使步数减少$2$

问题就变成了给区间$[l,r]$加首项为$1$，公差为$1$的等差数列
也就是给位置$l $的元素加$1$，位置$l+1$的元素加$2$，位置$l+2$的元素加$3$……位置$r$的元素加$r-l+1$
令$\text{cnt}[l]$加$1$,$\text{cnt}[r+1]$减$r-l+1+1$，$\text{cnt}[r+2]$减$r-l+1$
对$\rm cnt$做一遍前缀和，得到差分数组
再做一遍前缀和，可以得到本身的值
这个被称为二阶差分

两遍前缀和后的$\rm cnt$数组就是把位置选在$x$，会使原本的步数减少多少

取最大的一个，总步数减它就是答案

时间复杂度$O(n)$

Code:

Click to show/hide the code

#include <cstdio>
#include <iostream>
#include <cassert>
#include <algorithm>

using namespace std;
const int MAXN = 1e5 + 10;

int a[MAXN];
long long cnt[MAXN << 1];
int n, m;
inline void _read(int &x)
{
	x = 0;
	register char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
}

int main()
{
	_read(n), _read(m);
	for (register int i = 1; i <= n; ++i) _read(a[i]);
	
	long long tot = 0;
	for (register int i = 1, l, r; i < n; ++i)
	{
		l = a[i];
		r = a[i + 1];
		if (l > r) r += m;
		tot += r - l;
		if (r - l > 1)
		{
			cnt[l + 2]++;
			cnt[r + 1] -= r - (l + 2) + 2;
			cnt[r + 2] += r - (l + 2) + 1;
		}
	}
	for (register int i = 1; i <= m * 2; ++i) cnt[i] += cnt[i - 1];
	for (register int i = 1; i <= m * 2; ++i) cnt[i] += cnt[i - 1];
	register long long ans = tot;
	for (register int i = 1; i <= m; ++i) ans = min(ans, tot - cnt[i] - cnt[i + m]);
	return printf("%lld", ans), 0;
}